#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <algorithm>
#include <Vector.hpp>

using namespace std;
class Solution
{
public:
    vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries)
    {
        map<string, map<string, double>> graph;
        vector<double> res(queries.size());
        for (int i = 0; i < equations.size(); i++)
        {
            graph[equations[i][0]][equations[i][1]] = values[i];
            graph[equations[i][1]][equations[i][0]] = 1 / values[i];
        }
        for (int i = 0; i < queries.size(); i++)
        {
            res[i] = search(graph, queries[i][0], queries[i][1]);
        }
        return res;
    }

    double search(map<string, map<string, double>> &graph, string a, string b)
    {
        if (graph.find(a) == graph.end() || graph.find(b) == graph.end())
            return -1;
        if (a == b)
            return 1;
        map<string, bool> visited;
        for (auto edge : graph)
        {
            visited[edge.first] = false;
        }
        visited[a] = true;
        return dfs(graph, visited, a, b, 1);
    }

    double dfs(map<string, map<string, double>> &graph, map<string, bool> &visited, string a, string b, double value)
    {
        if (graph[a].find(b) != graph[a].end())
        {
            return value * graph[a][b];
        }
        for (auto edge : graph[a])
        {
            if (visited[edge.first] == true)
                continue;
            visited[edge.first] = true;
            double val = dfs(graph, visited, edge.first, b, value * edge.second);
            if (val != -1)
                return val;
        }
        return -1;
    }
};

int main()
{
    cout << "Code399" << endl;
    Solution s;
    vector<vector<string>> equations = {{"a", "b"}, {"b", "c"}, {"a", "c"}, {"d", "e"}};
    vector<double> values = {2.0, 3.0, 6.0, 1.0};
    vector<vector<string>> queries = {{"a", "c"}, {"b", "c"}, {"a", "e"}, {"a", "a"}, {"x", "x"}, {"a", "d"}};
    vector<double> res = s.calcEquation(equations, values, queries);
    PrintVector(res);
    return 0;
}
